class FreePartition:
    def __init__(self, start_addr, size):
        self.start_addr = start_addr
        self.size = size
        self.next = None

    def __repr__(self):
        return f"分区起始地址: {self.start_addr}, 大小: {self.size}KB"


class MemoryManager:
    def __init__(self, total_memory):
        self.total_memory = total_memory
        self.free_list = FreePartition(0, total_memory)

    def first_fit_allocate(self, job_size, job_id):
        prev = None
        current = self.free_list
        while current:
            if current.size >= job_size:
                # 分配内存
                if current.size == job_size:
                    # 完全分配，移除当前分区
                    if prev:
                        prev.next = current.next
                    else:
                        self.free_list = current.next
                else:
                    # 部分分配，更新当前分区
                    new_partition = FreePartition(current.start_addr + job_size, current.size - job_size)
                    if prev:
                        prev.next = new_partition
                    else:
                        self.free_list = new_partition
                    new_partition.next = current.next
                return current.start_addr
            prev = current
            current = current.next
        return -1  # 分配失败

    def best_fit_allocate(self, job_size, job_id):
        best_fit = None
        prev_best = None
        prev = None
        current = self.free_list

        while current:
            if current.size >= job_size:
                if not best_fit or current.size < best_fit.size:
                    best_fit = current
                    prev_best = prev
            prev = current
            current = current.next

        if best_fit:
            # 分配内存
            if best_fit.size == job_size:
                if prev_best:
                    prev_best.next = best_fit.next
                else:
                    self.free_list = best_fit.next
            else:
                new_partition = FreePartition(best_fit.start_addr + job_size, best_fit.size - job_size)
                if prev_best:
                    prev_best.next = new_partition
                else:
                    self.free_list = new_partition
                new_partition.next = best_fit.next
            return best_fit.start_addr
        return -1  # 分配失败

    def free_memory(self, start_addr, size):
        new_partition = FreePartition(start_addr, size)

        # 找到插入位置
        prev = None
        current = self.free_list
        while current and current.start_addr < start_addr:
            prev = current
            current = current.next

        # 插入新分区
        if prev:
            prev.next = new_partition
            new_partition.next = current
        else:
            new_partition.next = self.free_list
            self.free_list = new_partition

        # 合并相邻分区
        self._merge_adjacent_partitions()

    def _merge_adjacent_partitions(self):
        current = self.free_list
        while current and current.next:
            if current.start_addr + current.size == current.next.start_addr:
                # 合并当前分区和下一个分区
                current.size += current.next.size
                current.next = current.next.next
            else:
                current = current.next

    def display_free_list(self):
        partitions = []
        current = self.free_list
        while current:
            partitions.append(f"起始地址: {current.start_addr}KB, 大小: {current.size}KB")
            current = current.next
        if not partitions:
            print("空闲分区列表为空")
        else:
            print("空闲分区列表:")
            for i, p in enumerate(partitions):
                print(f"{i + 1}. {p}")


def run_simulation(algorithm='first_fit'):
    print(f"==== 开始内存分配模拟 ({algorithm.upper()}算法) ====")
    mm = MemoryManager(640)

    # 模拟作业请求序列
    requests = [
        (1, 130, 'allocate'),  # 作业1申请130KB
        (2, 60, 'allocate'),  # 作业2申请60KB
        (3, 100, 'allocate'),  # 作业3申请100KB
        (2, 60, 'free'),  # 作业2释放60KB
        (4, 200, 'allocate'),  # 作业4申请200KB
        (3, 100, 'free'),  # 作业3释放100KB
        (1, 130, 'free'),  # 作业1释放130KB
        (5, 140, 'allocate'),  # 作业5申请140KB
        (6, 60, 'allocate'),  # 作业6申请60KB
        (7, 50, 'allocate'),  # 作业7申请50KB
        (8, 60, 'allocate')  # 作业8申请60KB
    ]

    allocated_jobs = {}  # 记录已分配的作业

    for job_id, size, action in requests:
        print(f"\n--- 处理请求: 作业{job_id} {action.upper()} {size}KB ---")

        if action == 'allocate':
            if algorithm == 'first_fit':
                start_addr = mm.first_fit_allocate(size, job_id)
            else:
                start_addr = mm.best_fit_allocate(size, job_id)

            if start_addr != -1:
                print(f"✅ 作业{job_id}分配成功，起始地址: {start_addr}KB")
                allocated_jobs[job_id] = (start_addr, size)
            else:
                print(f"❌ 作业{job_id}分配失败，没有足够的内存")
        else:
            if job_id in allocated_jobs:
                start_addr, size = allocated_jobs[job_id]
                mm.free_memory(start_addr, size)
                print(f"✅ 作业{job_id}释放成功")
                del allocated_jobs[job_id]
            else:
                print(f"❌ 作业{job_id}未分配内存，无法释放")

        # 显示当前空闲分区
        mm.display_free_list()


if __name__ == "__main__":
    # 运行首次适应算法模拟
    run_simulation('first_fit')

    print("\n\n========================================\n\n")

    # 运行最佳适应算法模拟
    run_simulation('best_fit')